#include<iostream>
#include<vector>
#include<string>
using namespace std;


int minCostClimbingStairs(vector<int>& cost) {
    vector<int> dp(cost.size() + 1);
    for (int i = 2; i <= cost.size(); i++)
    {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[cost.size()];
}

int numDecodings(string s) {
    int n = s.size();
    vector<int> dp(n);
    if (s[0] == '0') return 0;
    else dp[0] = 1;
    if (s.size() == 1) return 1;
    if (s[1] == '0')
    {
        if (atoi(s.substr(0, 1).c_str()) * 10 + atoi(s.substr(1, 1).c_str()) < 27) dp[1] = 1;
        else return 0;
    }
    else
    {
        if (atoi(s.substr(0, 1).c_str()) * 10 + atoi(s.substr(1, 1).c_str()) < 27) dp[1] = 2;
        else dp[1] = 1;
    }
    for (int i = 2; i < n; i++)
    {
        int flag1 = 0, flag2 = 0;
        if (s[i] == '0') flag1 = 0;
        else flag1 = 1;
        if (atoi(s.substr(i - 1, 1).c_str()) * 10 + atoi(s.substr(i, 1).c_str()) < 27 && 10<=atoi(s.substr(i - 1, 1).c_str()) * 10 + atoi(s.substr(i, 1).c_str())) flag2 = 1;
        else flag2 = 0;
        if (flag1 && flag2) dp[i] = dp[i - 1] + dp[i - 2];
        if (flag1 && !flag2) dp[i] = dp[i - 1];
        if (!flag1 && flag2) dp[i] = dp[i - 2];
        if (!flag1 && !flag2) return 0;
    }
    return dp[n - 1];
}
int main()
{
    vector<int> v{ 10,15,20 };
    //minCostClimbingStairs(v);
    string s = "123";
    int n = atoi(s.substr(0, 1).c_str());
    /*for (int i = 0; i < s.size(); i++)
    {
        int temp = atoi(s.substr(i, 1).c_str());
        cout << temp << endl;
    }*/
    //cout << s.size();
    numDecodings("2101");
	return 0;
}